package org.bai.algorithm.hot.hard;

/**
 * @ClassName FindMedianSortedArrays
 * @Description 寻找两个正序数组的中位数
 * @Author bai
 * @Date 2021/7/18 21:47
 * @Version 1.0
 **/

import org.bai.algorithm.util.ArrayUtils;
import org.bai.algorithm.util.RevealUtil;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 **/
public class FindMedianSortedArrays {

    public static void main(String[] args) {
        int[] nums1 = ArrayUtils.buildIncreaseInt(10);
        int[] nums2 = ArrayUtils.buildIncreaseInt(5);
        RevealUtil.reveal(nums1);
        RevealUtil.reveal(nums2);
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        double result = 0d;
        int numLength1 = nums1.length;
        int numLength2 = nums2.length;
        int temporaryLength = numLength1 + numLength2;
        if ((temporaryLength & 1) == 0) {
            int midIndex1 = temporaryLength / 2;
            int midIndex2 = temporaryLength / 2 + 1;
            int medianSortedArrays1 = findMedianSortedArrays(nums1, nums2, midIndex1);
            int medianSortedArrays2 = findMedianSortedArrays(nums1, nums2, midIndex2);
            return (medianSortedArrays1 + medianSortedArrays2 + result) / 2;
        } else {
            int midIndex = temporaryLength / 2 + 1;
            return findMedianSortedArrays(nums1, nums2, midIndex);
        }
    }

    public static int findMedianSortedArrays(int[] nums1, int[] nums2, int index) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int index1 = 0;
        int index2 = 0;

        while (true) {
            //边界情况，当index1越界时，直接返回nums2的第k小元素
            if(index1 == len1) {
                return nums2[index2 + index - 1];
            }
            //边界情况，当index2越界时，直接返回nums1的第k小元素
            if(index2 == len2) {
                return nums1[index1 + index - 1];
            }
            //边界情况，k等于1时，返回nums1第一个元素和nums2第一个元素较小者
            if(index == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int half = index / 2;
            int newIndex1 = Math.min(index1 + half, len1) - 1;
            int newIndex2 = Math.min(index2 + half, len2) - 1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];

            if(pivot1 <= pivot2) {
                index -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }
            //如果nums2的小，则忽略掉nums2[0] - nums2[k/2-1]这些元素
            //再更新 k，k 要减去忽略掉的那些元素，index2也要更新，待下轮使用
            else {
                index -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}
